Concept
integer programming
Parents
Children
Branch And BoundBranch And CutCovering ProblemsCutting Plane MethodsDisjunctive Programming
25.9K
Publications
1.6M
Citations
39.8K
Authors
5.6K
Institutions
Branch-and-Cut Synthesis
1965 - 1972
The mid-to-late 1960s through early 1970s saw branch-and-bound and implicit enumeration as the dominant framework for discrete optimization, with tree-search and pruning addressing 0-1 problems, knapsack, scheduling, and facility-location. Additive and implicit enumeration approaches refined linear relaxations and pruning strategies, strengthening 0-1 IP search through Balas’ lineage and early cutting ideas. Cutting-plane inception and the emergence of branch-and-cut hybrids introduced powerful relaxations and guided enumeration, while zero-one specific algorithm families and canonical combinatorial problems provided essential testbeds for methodological development.
• Branch-and-bound and implicit enumeration dominated early IP methodology, using tree-search with pruning and surrogate constraints to solve 0-1, knapsack, scheduling, and facility-location problems [6], [17], [8], [19], [18], [5].
• Balas' additive/implicit enumeration lineage, with additive algorithms, Balas’ method, and early cutting ideas (filter/intersection cuts), used to tighten LP relaxations and prune search in 0-1 IP [1], [3], [6], [7], [20].
• Cutting-plane inception and branch-and-cut hybrids appeared, leveraging filter methods and intersection cuts to strengthen relaxations and guide enumeration in IP problems [7], [20], [9].
• Zero-one specific algorithm families emerged: additive algorithms for 0-1 LPs, multiphase-dual strategies, direct search on binary variables, and combinatorial programming formulations [1], [3], [4], [11].
• Canonical combinatorial problems (knapsack, sequencing, scheduling, facility-location) served as standard testbeds for IP methods, stimulating algorithmic development and comparative evaluation [13], [17], [19], [8], [15].
Dual-Guided Exact Integer Programming
1973 - 1979
Duality-Driven Decomposition
1980 - 1986
Polyhedral Branch-and-Cut Era
1987 - 2001
Decomposition-Based Exact IP
2002 - 2008
Decomposition-Driven Integer Programming
2009 - 2017
Truck-Drone Logistics Optimization
2018 - 2024